package leetcode.d_200_299;

public class P287 {
    class Solution {
        public int findDuplicate(int[] nums) {
            int slow = 0;
            int fast = 0;
            slow = nums[slow];
            fast = nums[nums[fast]];
            while(slow != fast) {
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            int pre1 = 0;
            int pre2 = slow;
            while(pre1 != pre2) {
                pre1 = nums[pre1];
                pre2 = nums[pre2];
            }
            return pre1;
        }
    }

    public static void main(String[] args) {
        P287.Solution solution = new P287().new Solution();
        int[] nums = {1,3,4,2,2};
        System.out.println(solution.findDuplicate(nums));
    }
}
